In many applications, robots are used to perform functions in place of humans or to assist humans in order to increase productivity and efficiency. One such application is order fulfillment, which is typically performed in a large warehouse filled with products to be shipped to customers who have placed their orders over the internet for home delivery. Fulfilling such orders in a timely, accurate and efficient manner is logistically challenging to say the least.
In an online Internet shopping application, for example, clicking the “check out” button in a virtual shopping cart creates an “order.” The order includes a listing of items that are to be shipped to a particular address. The process of “fulfillment” involves physically taking or “picking” these items from a large warehouse, packing them, and shipping them to the designated address.
An important goal of the order fulfillment process is thus to ship as many items in as short a time as possible. The process of receiving an order, planning its fulfillment, finding the storage shelf or bin, picking the product, and repeating the process for each item on the order, then delivering the order to a shipping station is repetitive and labor intensive. In a warehouse stocked with thousands or tens of thousands of items of rapidly turning inventory, robots play a critical role in ensuring timely and efficient order fulfillment. In addition, the products that will ultimately be shipped first need to be received in the warehouse and stored or “placed” in storage bins in an orderly fashion throughout the warehouse so they can be readily retrieved for shipping.
Using robots to perform picking and placing functions may be done by the robot alone or with the assistance of human operators. Picking and placing or stocking functions, whether or not performed with human interaction, requires that the robot navigate from its present location to a target product storage or “bin” location. Along the robot's goal path from present location to product storage bin, the robot typically encounters stationary and moving obstacles such as walls, shelves, support structure, humans and other robots. Furthermore, as new product is stocked and depleted, as new shelves and bins are added and removed, and as miscellaneous objects are introduced into the shared human-robot space, the dynamic nature of an order fulfillment warehouse requires constant updating of information about the warehouse and its contents.
Obstacle avoidance while navigating the robot's goal path involves computing a series of increment movements using information on nearby fixed and moving obstacles. The incremental movement must not drive the robot into an obstacle, fixed or moving, and the trajectory of the robot to drive its movement must be computed within a fixed cycle time. Known methods of robot navigation, however, choose between approaches better suited to navigating fixed obstacles and approaches better suited for navigating moving obstacles, i.e. robots. What is needed is a computationally efficient method for robot navigation considering both moving and fixed obstacles, thus improving the ability of the robot to make progress toward its target location in the allotted cycle time for each increment movement.